//
//  KMP.cpp
//  Algorithm
//
//  Created by 刘锦程 on 2023/9/20.
//

#include <stdio.h>
#include<string.h>
using namespace std;
string s1,s2;//s1是原始串，s2是模版串
int Next[100004];
void generateNext(){
    int prefix_len=0,i=1;
    Next[0]=prefix_len;
    while(s2[i]!=0){
        if(s2[i]==s2[prefix_len]){
            prefix_len++;
            Next[i]=prefix_len;
            i++;
        }else{
            if(prefix_len==0){
                Next[i]=0;
                prefix_len=0;
                i++;
            }else{
                prefix_len=Next[prefix_len-1];
            }
        }
        
    }
}
void kmp_search(){
    int i=0;
    int j=0;
    while(s1[i]!=0){
        if(s1[i]==s2[j]){
            i++;
            j++;
        }else if(j>0){
            j=Next[j-1];
        }else{
            i++;
        }
        if(j==s2.length()){
            cout<<i-j+1<<endl;
        }
    }
    
}
int KMP(){
    cin>>s1;
    getchar();
    cin>>s2;
    generateNext();
    kmp_search();
    int i=0;
    while(s2[i]!=0){
        cout<<Next[i++]<<" ";
    }
    cout<<endl;
    return 0;
}
